#define  _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//最长数对链
//这个题的逻辑和之前子序列的问题完全一样
//不一样的点在于不有序，也就是说不好确定状态转移方程，也就是前后dp之间的关系、
//当我们按照第一个元素的大小进行排序的时候就能解决我们的问题，证明如下{a,b}{c,d}
//排序之后c >= a,并且b一定大于a，d一定大于c，可以得到d>c>=a,也就是说第一个不可能排在第二个或者其他的后面，问题解决

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();
        sort(pairs.begin(), pairs.end());

        //创建dp表
        //初始化
        //填表
        //返回值

        vector<int> dp(n, 1);
        int ret = 1;
        for (int i = 1; i < n; i++)
        {
            for (int j = i - 1; j >= 0; j--)
            {
                if (pairs[j][1] < pairs[i][0]) dp[i] = max(dp[j] + 1, dp[i]);
                ret = max(dp[i], ret);
            }
        }
        return ret;

    }
};

int main()
{

	return 0;
}